This invention relates to three-dimensional (3D) graphics systems and more particularly to apparatus and methods for improving the efficiency of tile-based rasterization.
Rasterization is the process of taking a primitive (e.g., a triangle, line, point, polygon, etc.), described in vector format, and converting it to a raster image made up of pixels or dots. This raster image may then be provided to an output device such as a visual display or printer. Rasterization is currently the most widely used technique for generating real-time 3D computer graphics. This is primarily due to its high speed compared to other rendering techniques. Rasterization techniques must normally provide immediate response to user input in real-time applications and provide frame rates of at least twenty frames per second.
Currently, scanline rasterization is one of the most commonly used rasterization techniques. In this technique, the rasterizer converts a primitive to pixels one horizontal row, or scanline, at a time. In particular, this technique involves rasterizing a primitive into a frame buffer by “filling” the polygon one horizontal line at a time. This is typically performed by calculating runs or “spans” of pixels formed by the intersection of a scanline with the edges of the primitive. This technique typically requires a great deal of redundant computation, since each edge is checked for intersections with each successive scanline. To make scanline rasterization more efficient, optimization techniques such as active edge lists or tables have been introduced to track primitive edges that intersect with a scanline. This method, while much more efficient, is more complicated and thus more difficult to optimize.
An alternative technique to scanline rasterization is tiled-based rasterization. In this technique, a primitive is rasterized one block of pixels (i.e., one tile) at a time rather than one scanline at a time. A block or tile of pixels may include, for example a 4-by-4 block of sixteen pixels. Starting with an initial tile, valid pixels are determined for the tile. Once this tile is complete, the next tile is evaluated. This rasterization technique typically walks in a linear fashion, one tile at a time, horizontally from one edge of a primitive to the opposite edge. Upon reaching an edge, the next row of tiles either up or down from the previous row of tiles will be scanned. Each row of tiles will typically be evaluated in the same direction and sequence as the previous row. Unfortunately, this method for evaluating rows of tiles is not as efficient as it could be because it does not utilize cache memory effectively. In particular, this method for evaluating tiles reduces cache hits and breaks the cache utilization more than is necessary.
In view of the foregoing, what are needed are apparatus and methods for improving the efficiency of tile-based rasterization. More specifically, apparatus and methods are needed to improve cache utilization and thereby increase the frequency of cache hits when performing tile-based rasterization. Further needed are improved apparatus and methods for evaluating pixels within each tile when performing tile-based rasterization, thereby eliminating or reducing wasted cycles. Such apparatus and methods are disclosed and claimed herein.